package com.lizk.sort;

/**
 * @author lizhikui
 * @date 2020/2/7 13:19
 */
public class MergeSort {

    /**
     * 自上而下的递归排序
     *
     * 合并排序的逻辑
     * 1.把数组分为两个均等的数组，分开的数组继续分，直到分开的数组只有一个元素
     * 2.把分开的数组进行合并，合并为有序的数组，一次把所有分开的数组合并
     * 3.最终合并为一个数组。
     * 4.优化思路，当拆分的数组小到一定程度的时候，改用插入排序来处理。
     */
    public static Integer[] sort(Integer [] array){
        return merge2(array);
    }

    /**
     * 自底向上的方式循环排序
     */
    public static int[] sortFloorUp(int [] array){
        return null;
    }


    private static Integer[] merge (Integer[] a1 ,Integer [] a2){
        Integer[] a = new Integer[a1.length + a2.length];
        int i = 0 ;
        int j = 0 ;
        while (i + j < a1.length + a2.length) {
            if (i>=a1.length){
                a[i+j] = a2[j];
                j++;
            }else if (j>=a2.length){
                a[i+j] = a1[i];
                i++;
            }else if(a1[i] >= a2[j]){
                a[i+j] = a2[j];
                j++;
            }else{
                a[i+j] = a1[i];
                i++;
            }
        }
        return a;
    }

    private static Integer[] merge(Integer[] array){
        if (array.length>=2){
            int mid = array.length / 2;
            Integer[] a = SortUtils.split(array, 0, mid);
            Integer[] b = SortUtils.split(array,mid,array.length);
            a = merge(a);
            b = merge(b);
            if(a[a.length - 1] > b[0]){
                return merge(a,b);
            }else {
                //TODO 换一个合并数组的函数
                return merge(a,b);
            }
        }else{
            return array;
        }
    }

    /**
     * 优化的合并方法，在数据小到一定程度的时候，使用插入排序进行排序。
     */
    private static Integer[] merge2(Integer[] array){
        if (array.length>=16){
            int mid = array.length / 2;
            Integer[] a = SortUtils.split(array, 0, mid);
            Integer[] b = SortUtils.split(array,mid,array.length);
            a = merge(a);
            b = merge(b);
            if(a[a.length - 1] > b[0]){
                return merge(a,b);
            }else {
                //TODO 换一个合并数组的函数
                return merge(a,b);
            }
        }else{
            return InsertSort.sort(array);
        }
    }

}
